llm-token-visualizer 0.3.0

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.hpp>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>
#include <regex>
#include <iostream>
#include <memory>
#include <chrono>
#include <queue>

// Forward declarations
struct FactNode;
struct ClaimEdge;

// Boost Graph typedefs
typedef boost::adjacency_list<
    boost::vecS,           // OutEdgeList
    boost::vecS,           // VertexList  
    boost::bidirectionalS, // Directed
    FactNode,              // VertexProperties
    ClaimEdge              // EdgeProperties
> FactGraph;

typedef boost::graph_traits<FactGraph>::vertex_descriptor VertexDesc;
typedef boost::graph_traits<FactGraph>::edge_descriptor EdgeDesc;

// Fact verification result
enum class VerificationStatus {
    TRUE,
    FALSE,
    PARTIALLY_TRUE,
    UNVERIFIED,
    CONTRADICTORY
};

// Knowledge graph node representing a fact
struct FactNode {
    std::string entity;
    std::string fact_type;
    std::string content;
    double confidence_score;
    std::chrono::system_clock::time_point timestamp;
    std::unordered_set<std::string> tags;
    
    FactNode() : confidence_score(0.0) {}
    
    FactNode(const std::string& e, const std::string& ft, const std::string& c, double conf = 1.0)
        : entity(e), fact_type(ft), content(c), confidence_score(conf),
          timestamp(std::chrono::system_clock::now()) {}
};

// Edge representing relationships between facts
struct ClaimEdge {
    std::string relation_type;
    double weight;
    std::string evidence;
    
    ClaimEdge() : weight(1.0) {}
    
    ClaimEdge(const std::string& rt, double w = 1.0, const std::string& ev = "")
        : relation_type(rt), weight(w), evidence(ev) {}
};

// Claim extracted from LLM output
struct Claim {
    std::string text;
    std::string subject;
    std::string predicate;
    std::string object;
    double extraction_confidence;
    
    Claim(const std::string& t, const std::string& s, const std::string& p, 
          const std::string& o, double conf = 1.0)
        : text(t), subject(s), predicate(p), object(o), extraction_confidence(conf) {}
};

// Fact verification result
struct VerificationResult {
    VerificationStatus status;
    double confidence;
    std::vector<VertexDesc> supporting_facts;
    std::vector<VertexDesc> contradicting_facts;
    std::string explanation;
    
    VerificationResult() : status(VerificationStatus::UNVERIFIED), confidence(0.0) {}
};

class FactGraphEngine {
private:
    FactGraph knowledge_graph;
    std::unordered_map<std::string, VertexDesc> entity_index;
    std::vector<std::regex> claim_patterns;
    
    // Initialize common claim extraction patterns
    void initializePatterns() {
        claim_patterns = {
            std::regex(R"((\w+(?:\s+\w+)*)\s+(is|are|was|were|has|have|had)\s+(.+))"),
            std::regex(R"((\w+(?:\s+\w+)*)\s+(created|founded|invented|discovered)\s+(.+))"),
            std::regex(R"((\w+(?:\s+\w+)*)\s+(born|died|lived)\s+(.+))"),
            std::regex(R"((\w+(?:\s+\w+)*)\s+(located|situated)\s+in\s+(.+))"),
            std::regex(R"((\w+(?:\s+\w+)*)\s+(costs|priced|valued)\s+(.+))")
        };
    }
    
    // Extract structured claims from text using regex patterns
    std::vector<Claim> extractClaims(const std::string& text) {
        std::vector<Claim> claims;
        
        for (const auto& pattern : claim_patterns) {
            std::sregex_iterator iter(text.begin(), text.end(), pattern);
            std::sregex_iterator end;
            
            while (iter != end) {
                std::smatch match = *iter;
                if (match.size() >= 4) {
                    std::string subject = match[1].str();
                    std::string predicate = match[2].str();
                    std::string object = match[3].str();
                    
                    // Calculate extraction confidence based on pattern specificity
                    double confidence = 0.8; // Base confidence
                    
                    claims.emplace_back(match[0].str(), subject, predicate, object, confidence);
                }
                ++iter;
            }
        }
        
        return claims;
    }
    
    // Find matching facts in knowledge graph using graph traversal
    std::vector<VertexDesc> findMatchingFacts(const Claim& claim) {
        std::vector<VertexDesc> matches;
        
        // First, try exact entity match
        auto entity_it = entity_index.find(claim.subject);
        if (entity_it != entity_index.end()) {
            VertexDesc start_vertex = entity_it->second;
            
            // BFS to find related facts
            std::queue<VertexDesc> queue;
            std::unordered_set<VertexDesc> visited;
            
            queue.push(start_vertex);
            visited.insert(start_vertex);
            
            while (!queue.empty() && matches.size() < 10) { // Limit search depth
                VertexDesc current = queue.front();
                queue.pop();
                
                const FactNode& fact = knowledge_graph[current];
                
                // Check if this fact is relevant to the claim
                if (isFactRelevant(fact, claim)) {
                    matches.push_back(current);
                }
                
                // Add adjacent vertices to queue
                auto out_edges = boost::out_edges(current, knowledge_graph);
                for (auto ei = out_edges.first; ei != out_edges.second; ++ei) {
                    VertexDesc target = boost::target(*ei, knowledge_graph);
                    if (visited.find(target) == visited.end()) {
                        visited.insert(target);
                        queue.push(target);
                    }
                }
            }
        }
        
        // Fallback: semantic similarity search across all nodes
        if (matches.empty()) {
            auto vertices = boost::vertices(knowledge_graph);
            for (auto vi = vertices.first; vi != vertices.second; ++vi) {
                const FactNode& fact = knowledge_graph[*vi];
                if (isFactRelevant(fact, claim)) {
                    matches.push_back(*vi);
                }
            }
        }
        
        return matches;
    }
    
    // Check if a fact is relevant to a claim using text similarity
    bool isFactRelevant(const FactNode& fact, const Claim& claim) {
        // Simple relevance check - can be enhanced with NLP techniques
        std::string fact_text = fact.entity + " " + fact.content;
        std::string claim_text = claim.subject + " " + claim.predicate + " " + claim.object;
        
        // Convert to lowercase for comparison
        std::transform(fact_text.begin(), fact_text.end(), fact_text.begin(), ::tolower);
        std::transform(claim_text.begin(), claim_text.end(), claim_text.begin(), ::tolower);
        
        // Check for common words (simple jaccard similarity)
        std::regex word_regex(R"(\b\w+\b)");
        std::unordered_set<std::string> fact_words, claim_words;
        
        std::sregex_iterator iter1(fact_text.begin(), fact_text.end(), word_regex);
        std::sregex_iterator end;
        
        while (iter1 != end) {
            fact_words.insert(iter1->str());
            ++iter1;
        }
        
        std::sregex_iterator iter2(claim_text.begin(), claim_text.end(), word_regex);
        while (iter2 != end) {
            claim_words.insert(iter2->str());
            ++iter2;
        }
        
        // Calculate Jaccard similarity
        std::unordered_set<std::string> intersection;
        for (const auto& word : fact_words) {
            if (claim_words.find(word) != claim_words.end()) {
                intersection.insert(word);
            }
        }
        
        double jaccard = static_cast<double>(intersection.size()) / 
                        (fact_words.size() + claim_words.size() - intersection.size());
        
        return jaccard > 0.2; // Threshold for relevance
    }
    
    // Verify a single claim against matched facts
    VerificationResult verifyClaim(const Claim& claim, const std::vector<VertexDesc>& matching_facts) {
        VerificationResult result;
        
        if (matching_facts.empty()) {
            result.status = VerificationStatus::UNVERIFIED;
            result.explanation = "No matching facts found in knowledge base";
            return result;
        }
        
        double total_support = 0.0;
        double total_contradiction = 0.0;
        
        for (VertexDesc vertex : matching_facts) {
            const FactNode& fact = knowledge_graph[vertex];
            
            // Simple fact verification logic - can be enhanced
            bool supports = checkFactSupport(fact, claim);
            bool contradicts = checkFactContradiction(fact, claim);
            
            if (supports) {
                result.supporting_facts.push_back(vertex);
                total_support += fact.confidence_score;
            }
            
            if (contradicts) {
                result.contradicting_facts.push_back(vertex);
                total_contradiction += fact.confidence_score;
            }
        }
        
        // Determine verification status
        if (total_support > total_contradiction) {
            if (total_contradiction > 0) {
                result.status = VerificationStatus::PARTIALLY_TRUE;
            } else {
                result.status = VerificationStatus::TRUE;
            }
        } else if (total_contradiction > total_support) {
            result.status = VerificationStatus::FALSE;
        } else if (total_support > 0 && total_contradiction > 0) {
            result.status = VerificationStatus::CONTRADICTORY;
        }
        
        result.confidence = std::max(total_support, total_contradiction) / matching_facts.size();
        
        // Generate explanation
        result.explanation = generateExplanation(result, claim);
        
        return result;
    }
    
    // Check if a fact supports a claim
    bool checkFactSupport(const FactNode& fact, const Claim& claim) {
        // Simplified support check - look for semantic alignment
        std::string fact_content = fact.content;
        std::string claim_content = claim.object;
        
        std::transform(fact_content.begin(), fact_content.end(), fact_content.begin(), ::tolower);
        std::transform(claim_content.begin(), claim_content.end(), claim_content.begin(), ::tolower);
        
        return fact_content.find(claim_content) != std::string::npos ||
               claim_content.find(fact_content) != std::string::npos;
    }
    
    // Check if a fact contradicts a claim
    bool checkFactContradiction(const FactNode& fact, const Claim& claim) {
        // Simplified contradiction detection
        std::vector<std::string> contradiction_indicators = {
            "not", "never", "false", "incorrect", "wrong", "opposite"
        };
        
        std::string fact_content = fact.content;
        std::transform(fact_content.begin(), fact_content.end(), fact_content.begin(), ::tolower);
        
        for (const auto& indicator : contradiction_indicators) {
            if (fact_content.find(indicator) != std::string::npos) {
                return true;
            }
        }
        
        return false;
    }
    
    // Generate human-readable explanation
    std::string generateExplanation(const VerificationResult& result, const Claim& claim) {
        std::string explanation = "Claim: \"" + claim.text + "\"\n";
        
        switch (result.status) {
            case VerificationStatus::TRUE:
                explanation += "Status: TRUE - Supported by " + std::to_string(result.supporting_facts.size()) + " facts\n";
                break;
            case VerificationStatus::FALSE:
                explanation += "Status: FALSE - Contradicted by " + std::to_string(result.contradicting_facts.size()) + " facts\n";
                break;
            case VerificationStatus::PARTIALLY_TRUE:
                explanation += "Status: PARTIALLY TRUE - Mixed evidence found\n";
                break;
            case VerificationStatus::CONTRADICTORY:
                explanation += "Status: CONTRADICTORY - Conflicting evidence\n";
                break;
            case VerificationStatus::UNVERIFIED:
                explanation += "Status: UNVERIFIED - Insufficient evidence\n";
                break;
        }
        
        explanation += "Confidence: " + std::to_string(result.confidence);
        return explanation;
    }
    
public:
    FactGraphEngine() {
        initializePatterns();
    }
    
    // Add a fact to the knowledge graph
    VertexDesc addFact(const std::string& entity, const std::string& fact_type, 
                      const std::string& content, double confidence = 1.0) {
        VertexDesc vertex = boost::add_vertex(knowledge_graph);
        knowledge_graph[vertex] = FactNode(entity, fact_type, content, confidence);
        
        // Index by entity for quick lookup
        entity_index[entity] = vertex;
        
        return vertex;
    }
    
    // Add relationship between facts
    void addRelation(VertexDesc from, VertexDesc to, const std::string& relation_type,
                    double weight = 1.0, const std::string& evidence = "") {
        boost::add_edge(from, to, ClaimEdge(relation_type, weight, evidence), knowledge_graph);
    }
    
    // Main fact-checking function
    std::vector<VerificationResult> checkFacts(const std::string& llm_output) {
        auto start_time = std::chrono::high_resolution_clock::now();
        
        // Extract claims from LLM output
        std::vector<Claim> claims = extractClaims(llm_output);
        std::vector<VerificationResult> results;
        
        // Verify each claim
        for (const auto& claim : claims) {
            std::vector<VertexDesc> matching_facts = findMatchingFacts(claim);
            VerificationResult result = verifyClaim(claim, matching_facts);
            results.push_back(result);
        }
        
        auto end_time = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
        
        std::cout << "Fact-checking completed in " << duration.count() << "ms\n";
        std::cout << "Processed " << claims.size() << " claims\n";
        
        return results;
    }
    
    // Get graph statistics
    void printGraphStats() {
        std::cout << "Knowledge Graph Statistics:\n";
        std::cout << "Vertices: " << boost::num_vertices(knowledge_graph) << "\n";
        std::cout << "Edges: " << boost::num_edges(knowledge_graph) << "\n";
        std::cout << "Indexed entities: " << entity_index.size() << "\n";
    }
    
    // Load sample knowledge base
    void loadSampleKnowledgeBase() {
        // Add sample facts
        auto paris_vertex = addFact("Paris", "location", "capital of France", 0.95);
        auto france_vertex = addFact("France", "country", "European nation", 0.98);
        auto eiffel_vertex = addFact("Eiffel Tower", "landmark", "iron tower in Paris built in 1889", 0.99);
        auto einstein_vertex = addFact("Albert Einstein", "person", "theoretical physicist born in 1879", 0.99);
        auto relativity_vertex = addFact("Theory of Relativity", "scientific theory", "developed by Einstein in 1905", 0.95);
        
        // Add relationships
        addRelation(paris_vertex, france_vertex, "capital_of", 0.95);
        addRelation(eiffel_vertex, paris_vertex, "located_in", 0.99);
        addRelation(relativity_vertex, einstein_vertex, "developed_by", 0.95);
        
        std::cout << "Sample knowledge base loaded successfully!\n";
    }
};

// Example usage and testing
int main() {
    std::cout << "=== FactGraph: Real-Time Fact-Checking DAG Engine ===\n\n";
    
    FactGraphEngine engine;
    
    // Load sample knowledge base
    engine.loadSampleKnowledgeBase();
    engine.printGraphStats();
    
    std::cout << "\n=== Testing Fact-Checking ===\n";
    
    // Test with sample LLM output containing various claims
    std::string llm_output = R"(
        Paris is the capital of France and home to many landmarks.
        The Eiffel Tower was built in 1889 and is located in Paris.
        Albert Einstein developed the Theory of Relativity in 1905.
        The moon is made of cheese and orbits the Earth.
        Tokyo is the largest city in Japan.
    )";
    
    std::cout << "Input text: " << llm_output << "\n\n";
    
    // Perform fact-checking
    auto results = engine.checkFacts(llm_output);
    
    // Display results
    std::cout << "\n=== Verification Results ===\n";
    for (size_t i = 0; i < results.size(); ++i) {
        std::cout << "\n--- Result " << (i + 1) << " ---\n";
        std::cout << results[i].explanation << "\n";
    }
    
    return 0;
}